package com.zjsru.studyplan1;

import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和 II - 输入有序数组
 * <p>
 * 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 */

public class twosum {
    
    /**
     * 两数之和：暴力模拟
     *
     * @param numbers 数字
     * @param target  目标
     * @return {@link int[]}
     */
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, rigth = numbers.length - 1;
        for (int i = left, j = rigth; i < j; ) {
            int sum = numbers[i] + numbers[j];
            if (sum > target) {
                j--;
            } else if (sum < target) {
                i++;
            } else if (sum == target) {
                return new int[] {i + 1, j + 1};//下标从1开始计数
            }
        }
        return null;
        
    }
    
    /**
     * 增加哈希map做法。
     *
     * @param numbers 数字
     * @param target  目标
     * @return {@link int[]}
     */
    public int[] twoSumMap(int[] numbers, int target) {
        int[] ans = new int[2];
        //按照数组值为Key存入map，来获取value为下标数组的值
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int number = numbers[i];
            if (map.containsKey(target - number)) {
                ans[0] = i;
                ans[1] = map.get(target - number);
            }
            map.put(number, i);
        }
        return ans;
        
    }
    
    public static void main(String[] args) {
        twosum twosum = new twosum();
        int[] nums = new int[] {5, 25, 75};
        int target = 100;
        System.out.println(twosum.twoSum(nums, target));
    }
}
